package cn.springcloud.fix.demo.leecode;

import com.sun.org.apache.regexp.internal.RE;

public class IsPalindrome {

    public static void main(String[] args) {
        int flag = climbStairs2(5);
        System.out.println(1221 % 1000);
    }

    public static int climbStairs2(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs2(n - 1) + climbStairs2(n - 2);
    }

    //爬楼梯，一次只能爬一阶或者两阶
    //第n个台阶只能从第n-1或者n-2个上来。
    //到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去。
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int i1 = 1;
        int i2 = 2;

        //第3个台阶只能从第1或者2个台阶上来，到第3个台阶的走法 = 到第1个台阶的走法 + 第2个台阶的走法
        //第4个台阶只能从第2或者3个台阶上来，到第4个台阶的走法 = 到第2个台阶的走法 + 第3个台阶的走法
        for (int i = 3; i <= n; i++) {
            int temp = i1 + i2;
            i1 = i2;
            i2 = temp;
        }
        return i2;
    }

    //回文数
    public static boolean isPalindrome(int x) {
        String a = String.valueOf(x);
        int len = a.length();
        int middle = len / 2;
        for (int i = 0; i <= middle; i++) {
            char s1 = a.charAt(i);
            char s2 = a.charAt(len - 1 - i);
            if (s1 != s2) {
                return false;
            }
        }
        return true;
    }

    //回文数，比如 121
    public static boolean isPalindrome2(int x) {
        if (x < 0) return false;
        int div = 1;

        // 121/100=1   121%10=1    121%100/10=2
        // 1221/1000=1  1221%10=1   1221%1000=221/10=22 去掉首尾数字
        while (x / div >= 10) {
            div = div * 10;
        }

        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) {
                return false;
            }
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}
